import java.util.*;
public class MinimumTotal {
    // public int minimumTotal(List<List<Integer>> triangle) {
    //   int n = triangle.size();
    //   if(n == 0) return 0;
    //   int[][] dp = new int[n][n];
    //   dp[0][0] = triangle.get(0).get(0);
    //   for(int i = 1; i < n; i++) {
    //     for(int j = 0; j <= i; j++) {
    //       int left = j == 0 ? Integer.MAX_VALUE : dp[i-1][j-1];
    //       int right = j == i ? Integer.MAX_VALUE : dp[i-1][j];
    //       int top = Math.min(left, right);
          
    //       dp[i][j] = triangle.get(i).get(j) + top;
    //     }
    //   }
    //   int res = Integer.MAX_VALUE;
    //   for(int i = 0; i < n; i++) {
    //     res = Math.min(res, dp[n-1][i]);
    //   }
    //   return res;
    // }

    public int minimumTotal(List<List<Integer>> triangle) {
      int n = triangle.size();
      if(n == 0) return 0;
      int[] dp = new int[n];
      dp[0] = triangle.get(0).get(0);
      
      for(int i = 1; i < n; i++) {
        for(int j = i; j >= 0; j--) {
          int left = j == 0 ? Integer.MAX_VALUE : dp[j-1];
          int right = j == i ? Integer.MAX_VALUE : dp[j];
          dp[j] = Math.min(left, right) + triangle.get(i).get(j);
        }
      }
      int res = Integer.MAX_VALUE;
      for(int i = 0; i < n; i++) {
        res = Math.min(res, dp[i]);
      }
      return res;
    }
    public static void main(String[] args) {
      List<List<Integer>> triangle = new ArrayList<>();
      triangle.add(Arrays.asList(2));
      triangle.add(Arrays.asList(3, 4));
      triangle.add(Arrays.asList(6, 5, 7));
      triangle.add(Arrays.asList(4, 1, 8, 3));
      System.out.println(new MinimumTotal().minimumTotal(triangle));
    }
}


// 给定一个三角形 triangle ，找出自顶向下的最小路径和。

// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

 

// 示例 1：

// 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
// 输出：11
// 解释：如下面简图所示：
//    2
//   3 4
//  6 5 7
// 4 1 8 3
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// 示例 2：

// 输入：triangle = [[-10]]
// 输出：-10
 

// 提示：

// 1 <= triangle.length <= 200
// triangle[0].length == 1
// triangle[i].length == triangle[i - 1].length + 1
// -104 <= triangle[i][j] <= 104
 

// 进阶：

// 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
